'''
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路：首先查找起点然后根据规则获取结果集然后筛选出可行的路径，然后回溯递归
'''
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        for i, v in enumerate(matrix):
            # 查找路径起点
            if v == path[0] and self.notVisited([(i // cols, i % cols)], matrix, rows, cols, path): return True
        return False

    def notVisited(self, sites, matrix, rows, cols, path):
        if not sites: return False
        if len(sites) == len(path): return True
        # 新添加的坐标 作为新的起点
        x, y = sites[-1]
        # 获取可操作范围
        sets = [(i, j) for i, j in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]
                if 0 <= i < rows and 0 <= j < cols and  # 限定值范围
                (i, j) not in sites and matrix[i * cols + j] == path[len(sites)]]  # 设置走过的不能再走，而且要保持与path点值相等
        flag = sum([self.notVisited(sites + [site], matrix, rows, cols, path) for site in sets])  # 回溯递归
        return flag

s = Solution()
print(s.hasPath("ABCESFCSADEE",3,4,"SEE"))